#ifndef _OH_FOREST_H
#define _OH_FOREST_H

#include <oh/base.h>
#include <oh/iterator.h>
#include <oh/storage.h>
#include <oh/policy/access.h>
#include <oh/policy/navigation.h>

_OH_BEGIN
//----------------------------------------
// forward declaraions
//----------------------------------------
template <typename element>
class forest;

//----------------------------------------
// class forest
//----------------------------------------
template <typename T>
class forest{
public:
    typedef T               element;
    typedef unsigned int    size_type;
    typedef T *             pointer;
    typedef T const *       const_pointer;
    typedef T &             reference;
    typedef T const&        const_reference;

private:
    class node;

public:
    typedef iterator<node, policy::access::Read,    policy::navigation::Reverse_Bidirectional> const_reverse_iterator;
    typedef iterator<node, policy::access::Modify,  policy::navigation::Reverse_Bidirectional> reverse_iterator;
    typedef iterator<node, policy::access::Read,    policy::navigation::Bidirectional>	const_iterator;
    typedef iterator<node, policy::access::Modify,  policy::navigation::Bidirectional>	iterator;

private:
    class node
		:public Storage<element>
	{
    public:
        typedef signed int  difference;

    public:
        node()
            :Storage()
            ,pNext   (NULL)
            ,pPrev   (NULL)
            ,pLocalEnd(NULL)
            ,pParent (NULL)
        {
			pNext = this;
			pPrev = this;
			pLocalEnd = this;
			pParent = this;
		}
		template<class ActualType>
        node(node const*const a_pAt, ActualType const& a_Value, typename SelectTypeIf<CONVERTS(ActualType, element), bool, void>::Result const a_Compatibility = true)
            :Storage(a_Value)
			,pNext   (a_pAt)
            ,pPrev   (a_pAt->pPrev)
            ,pLocalEnd(pNext)
            ,pParent (pPrev)
        {
            pNext->pPrev = this;
            pPrev->pNext = this;

			pLocalEnd = pNext;
			pParent	  = pPrev;
        }
		template<class ActualType>
		node(node const*const a_pAt, ActualType * a_pValue, typename SelectTypeIf<CONVERTS(ActualType, element), bool, void>::Result const a_Compatibility = true)
			:Storage(a_pValue)
            ,pNext   (a_pAt)
            ,pPrev   (a_pAt->pPrev)
            ,pLocalEnd(pNext)
            ,pParent (pPrev)
        {
            pNext->pPrev = this;
            pPrev->pNext = this;

			pLocalEnd = pNext;
			pParent	  = pPrev;
        }
        node(node const*const a_pAt, node const& a_Node)
            :Storage(a_Node)
			,pNext (a_pAt)
            ,pPrev (a_pAt->pPrev)
            ,pLocalEnd(pNext)
            ,pParent(pPrev)
        {
            pNext->pPrev = this;
            pPrev->pNext = this;

			pLocalEnd = pNext;
			pParent   = pPrev;

			for(node const* pIn = a_Node.pNext; pIn != a_Node.pLocalEnd; pIn = pIn->pLocalEnd)
			{
				node const* pNew = new node(a_pAt, *pIn);
				pNew->pParent = this;
				pNew->_FixLocalEndsTo();
			}
        }
		// TODO: check better options
		void move(node const*const a_pAt) const
		{
			_Exclude();
			_Insert(a_pAt);
		}
        ~node()
        {
			_Exclude( );
			_ClearChildren( );
        }

    // For iterator needs
        node const& next( ) const
        {
            return *pNext;
        }
        node const& prev( ) const
        {
            return *pPrev;
        }
        node const& localend( ) const
        {
            return *pLocalEnd;
        }
        node const& parent( ) const
        {
            return *pParent;
        }
        const_reference operator* ( ) const
        {
            return peek();
        }
        const_pointer operator-> ( ) const
        {
            return &(peek());
        }
        reference operator* ( )
        {
            return gain();
        }
        pointer operator-> ( )
        {
            return &(gain());
        }
        bool operator== (node const& a_Node) const
        {
            return this == &a_Node;
        }
        bool operator!= (node const& a_Node) const
        {
            return !(*this == a_Node);
        }

    private:
        mutable node const*    pNext;
        mutable node const*    pPrev;
        mutable node const*    pLocalEnd;
        mutable node const*    pParent;

	private:
		void _Exclude() const
		{
			pPrev->pNext = pLocalEnd;
			node const*const pTmpPrev = pPrev;
			pPrev = pLocalEnd->pPrev;
			pPrev->pNext = this;
			pLocalEnd->pPrev = pTmpPrev;

            // Relink Local Ends
			pLocalEnd->_FixLocalEndsTo();

			// TODO: deal with hidden bug in FixLocalEndsTo
			_FixLocalEndsTo();
			pParent = this;
		}
		// Use this method carefully
		// TODO: test sentinel against this method
		void _Insert(node const*const a_pAt) const
		{
			node const*const pPrevTmp = a_pAt->pPrev;
			pPrevTmp->pNext = this;
			pPrev->pNext = a_pAt;
			a_pAt->pPrev = pPrev;
			pPrev = pPrevTmp;

			pParent = pPrev;

			a_pAt->_FixLocalEndsTo();
		}
		void _FixLocalEndsTo() const
		{
			for(node const* pTarget = pPrev; pTarget != pParent; pTarget = pTarget->pParent )
				pTarget->pLocalEnd = this;
		}
		void _ClearChildren() const
		{
            // Clear children
            node const* pTarget = pNext;
            while(pTarget != pLocalEnd)
            {
                node const*const pTmp = pTarget;
                pTarget = pTarget->pLocalEnd;
                delete pTmp;
			}
		}

    private:
        node(node const& a_Node);
        node& operator= (node const& a_Node);
    };

public:
// Common Iterators
    forest( )
        :_Sentinel( )
    {}
    forest(forest const& a_Forest)
        :_Sentinel( )
    {
		for(const_iterator it = a_Forest.begin();
						   it!= a_Forest.end();
						   it = end_of(it))
			insert(end(), it);
    }
    ~forest( )
    {
        clear();
    }
    forest & operator= (forest const& a_Forest)
    {
        if(*this == a_Forest)
            return *this;

        clear();
		for(const_iterator it = a_Forest.begin();
						   it!= a_Forest.end();
						   it = end_of(it))
			insert(end(), it);

        return *this;
    }
    bool operator== (forest const& a_Forest)
    {
        return (this == &a_Forest);
    }
    bool operator!= (forest const& a_Forest)
    {
        return !(*this == a_Forest);
    }

    // TODO:
    // work around push/pop front/back etc.

    const_iterator const begin( ) const
    {
        return const_iterator(_Sentinel.next());
    }
    iterator const begin( )
    {
        return iterator(_Sentinel.next());
    }
    const_iterator const end( ) const
    {
        return const_iterator(_Sentinel);
    }
    iterator const end( )
    {
        return iterator(_Sentinel);
    }
    const_reverse_iterator const rbegin( ) const
    {
        return const_reverse_iterator(_Sentinel.prev());
    }
    reverse_iterator const rbegin( )
    {
        return reverse_iterator(_Sentinel.prev());
    }
    const_reverse_iterator const rend( ) const
    {
        return const_reverse_iterator(_Sentinel);
    }
    reverse_iterator const rend( )
    {
        return reverse_iterator(_Sentinel);
    }
    bool empty() const
    {
        return begin()==end();
    }
    size_type const size() const
    {
		size_type Size = 0;
		for(const_iterator it = begin(); it!=end(); ++it)
			++Size;
        return Size;
    }
	size_type const height() const
	{
		size_type Height = 0;
		for(const_iterator it = begin(); it!=end(); it = end_of(it))
			Height = max(Height, height_of(it));
        return Height;
	}
    void clear()
    {
        while(begin() != end())
            erase(begin());
    }
    
// Sructure modify methods
    template<class ActualType>
    iterator const
    insert(
        const_iterator  const& a_pWhere,
        ActualType const&      a_Value,
	typename SelectTypeIf<CONVERTS(ActualType, element), bool, void>::Result const a_Compatibility = true)
    {
        return iterator(*(new node(&GetIteratorNode<node>(a_pWhere), a_Value)));
    }

    iterator const
    insert(
        const_iterator  const& a_pWhere,
        const_iterator  const& a_pRoot)
    {
        return iterator(*(new node(&GetIteratorNode<node>(a_pWhere), GetIteratorNode<node>(a_pRoot))));
    }

    iterator const
    erase(
        const_iterator const& a_pWhere)
    {
		node const& Where = GetIteratorNode<node>(a_pWhere);
        iterator const pTmp = iterator(Where.localend());
        delete &Where;
        return pTmp;
    }

	iterator const
	move(
		const_iterator const& a_pWhere,
		const_iterator const& a_pRoot)
	{
		node const& At     = GetIteratorNode<node>(a_pWhere);
		node const& Target = GetIteratorNode<node>(a_pRoot);
		Target.move(&At);
		return iterator(Target);
	}

	template<class ActualType>
    iterator const
    adopt(
        const_iterator  const& a_pWhere,
		ActualType & a_Value,
		typename SelectTypeIf<CONVERTS(ActualType, element), bool, void>::Result const a_Compatibility = true)
    {
        return iterator(*(new node(&GetIteratorNode<node>(a_pWhere), &a_Value)));
    }

    template<class ActualType>
    iterator const
    add_child(
        const_iterator  const& a_pWhere,
        ActualType const&      a_Value,
	typename SelectTypeIf<CONVERTS(ActualType, element), bool, void>::Result const a_Compatibility = true)
    {
        return iterator(*(new node(&(GetIteratorNode<node>(a_pWhere).next()), a_Value)));
    }
// Structure modufy methods, reverse order
	template<class ActualType>
    reverse_iterator const
    insert(
        const_reverse_iterator  const& a_pWhere,
        ActualType const & a_Value,
		typename SelectTypeIf<CONVERTS(ActualType, element), bool, void>::Result const a_Compatibility = true)
    {
        return reverse_iterator(*(new node(&(GetIteratorNode<node>(a_pWhere).next()), a_Value)));
    }

    reverse_iterator const
    insert(
        const_reverse_iterator  const& a_pWhere,
        const_reverse_iterator  const& a_pRoot)
    {
        return iterator(*(new node(&(GetIteratorNode<node>(a_pWhere).next()), GetIteratorNode<node>(a_pRoot))));
    }

    reverse_iterator const
    erase(
        const_reverse_iterator const& a_pWhere)
    {
		node const& Where = GetIteratorNode<node>(a_pWhere);
        iterator const pTmp = reverse_iterator(Where.prev());
        delete &Where;
        return pTmp;
    }

	reverse_iterator const
	move(
		const_reverse_iterator const& a_pWhere,
		const_reverse_iterator const& a_pRoot)
	{
		node const& At     = GetIteratorNode<node>(a_pWhere).next();
		node const& Target = GetIteratorNode<node>(a_pRoot);
		Target.move(&At);
		return reverse_iterator(Target);
	}

	template<class ActualType>
    reverse_iterator const
    adopt(
        const_reverse_iterator  const& a_pWhere,
        ActualType & a_Value,
		typename SelectTypeIf<CONVERTS(ActualType, element), bool, void>::Result const a_Compatibility = true)
    {
        return reverse_iterator(*(new node(&(GetIteratorNode<node>(a_pWhere).next()), &a_Value)));
    }

    template<class ActualType>
    reverse_iterator const
    add_child(
        const_reverse_iterator  const& a_pWhere,
        ActualType const&      a_Value,
	typename SelectTypeIf<CONVERTS(ActualType, element), bool, void>::Result const a_Compatibility = true)
    {
        return reverse_iterator(*(new node(&(GetIteratorNode<node>(a_pWhere).next()), a_Value)));
    }

    static const_iterator const end_of(const_iterator const& a_pRoot)
    {
        return iterator(GetIteratorNode<node>(a_pRoot).localend());
    }
    static const_iterator const parent_of(const_iterator const& a_pRoot)
    {
        return iterator(GetIteratorNode<node>(a_pRoot).parent());
    }
	static size_type const depth_of(const_iterator const& a_pRoot)
	{
		size_type depth = 0;
		const_iterator pIter = a_pRoot;
		do
		{
			++depth;
			pIter = parent_of(pIter);
		}while( pIter!=parent_of(pIter) );
		return --depth;
	}
	static size_type const size_of(const_iterator const& a_pRoot)
	{
		size_type Size = 0;
		for(const_iterator pIter = a_pRoot; pIter!=end_of(a_pRoot); ++pIter)
			++Size;
		return Size;
	}
	static bool const has_children(const_iterator const& a_pRoot)
	{
		return (++const_iterator(a_pRoot) == end_of(a_pRoot));
	}
	static size_type const height_of(const_iterator const& a_pRoot)
	{
		size_type max_depth = 0;
		for(const_iterator pIter = a_pRoot; pIter != end_of(a_pRoot); ++pIter)
			max_depth = max(depth_of(pIter), max_depth);

		return (++max_depth - depth_of(a_pRoot));
	}

// Data
private:
    node const  _Sentinel;

}; // class tree

_OH_END

#endif // _OH_TREE_H